home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15247 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: news.ccs.queensu.ca!news
  2. From: Wintermute <3mal5@qlink.queensu.ca>
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: fast find algoritm?
  5. Date: Thu, 04 Apr 1996 08:08:11 -0500
  6. Organization: System Infinity
  7. Message-ID: <3163C9BB.3829@qlink.queensu.ca>
  8. References: <Dp8wE7.8E3@cix.compulink.co.uk> <4juj1r$kt8@bilbo.nask.org.pl> <4k01ui$sl2@grimsel.zurich.ibm.com>
  9. NNTP-Posting-Host: qlink.queensu.ca
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0 (X11; I; qlink 5.4 sun4d)
  14.  
  15. Keith Whittingham wrote:
  16. > 
  17. > In <4juj1r$kt8@bilbo.nask.org.pl>, flssoft@blue.maloka.waw.pl (Grzegorz (FLS)) writes:
  18. > >setheridge@cix.compulink.co.uk ("Stephen Etheridge") wrote:
  19. > >
  20. > >>Does anyone have an search algoritm faster than a binary chop for the
  21. > >>following:
  22. > >Yes, there is an algorithm with cost O(1). Use a hash-table. If you
  23. > >use a good hash-function, you will have a fastest algorithm.
  24. > >
  25. > 
  26. > I doubt this is faster than a binary chop it the storage mechanism is
  27. > efficient and with only 1500 entries...
  28. > 
  29. > Keith
  30.  
  31. 2^11 = 2048, so you need at least 11 binary chops to search the table.
  32. With pointer dereferencing, etc., that'll likely take longer than a quick
  33. hash function.
  34.  
  35. The hash function, however, will require some sort of collision resolution
  36. scheme.  That can be avoided if your data is really random and your hash
  37. function is good, or perhaps you can even design a quick perfect hash
  38. function, the ideal.
  39.  
  40. In the final analysis, you can easily calculate the worst case for a
  41. binary search, by which I mean summing the number of comparisons and
  42. additions and function calls required.
  43.  
  44. Then you can do the same for the hash function, and obtain an average (or
  45. worst case) measurement for collision frequencies.  Just use the best.
  46. Hope this helps.
  47.  
  48. --
  49. Wintermute  <3mal5@qlink.queensu.ca>  <http://qlink.queensu.ca/~3mal5/>
  50.  
  51. "If I really knew how to write, I could write something that someone 
  52. could read and it would kill them."  -  william s. burroughs
  53.